Search for: All records

Range-filtering approximate nearest neighbor search (RFANNS) has gained significant attention recently. Consider a setDof high-dimensional vectors, each associated with a numeric attribute value, e.g., price or timestamp. An RFANNS query consists of a query vectorqand a query range, reporting the approximate nearest neighbors ofqamong data vectors whose attributes fall in the query range. Existing work on RFANNS only considers a static setDof data vectors while in many real-world scenarios, vectors arrive in the system in an arbitrary order. This paper studies dynamic RFANNS where both data vectors and queries arrive in a mixed stream: a query is posed on all the data vectors that have already arrived in the system. Existing work on RFANNS is difficult to be extended to the streaming setting as they construct the index in the order of the attribute values while the vectors arrive in the system in an arbitrary order. The main challenge to the dynamic RFANNS lies in the difference between the two orders. A naive approach to RFANNS maintains multiple hierarchical navigable small-world (HNSW) graphs, one for each of theO(|D|²) possible query ranges - too expensive to construct and maintain. To design an index structure that can integrate new data vectors with a low index size increment for efficient and effective query processing, we propose a structure calleddynamic segment graph.It compresses the set of HNSW graphs of the naive approach, proven to be lossless under certain conditions, with only a linear to log |D| new edges in expectation when inserting a new vector. This dramatically reduces the index size while largely preserving the search performance. We further propose heuristics to significantly reduce the index cost of our dynamic segment graph in practice. Extensive experimental results show that our approach outperforms existing methods for static RFANNS and is scalable in handling dynamic RFANNS. 

Abstract Swarm manufacturing is an emerging manufacturing paradigm that employs a heterogeneous swarm of robots to accomplish complex hybrid manufacturing tasks. Cooperative 3D printing (C3DP), a specialized form of swarm manufacturing, enables multiple printers to collaboratively produce large-scale parts, addressing key tradeoffs in additive manufacturing, such as size, speed, quality, and cost. A fundamental challenge in C3DP is ensuring collision-free, time-optimal printing in a shared workspace. This is a complex problem that can be influenced by factors such as the number of printers, part geometry, printer positioning, mobility, and kinematics. In this article, we present SafeZone*, a collision-free and scalable C3DP framework that optimizes printing time by co-considering the geometry (area and shape) and topology (space-connectivity) of a shared workspace during layer partitioning. We first establish a conceptual framework to mathematically represent the topology of a layer through partition graphs. Then, we use a Voronoi tessellation within a constrained optimization framework to control the partition graph and minimize makespan. The Voronoi sites are associated with printer locations, allowing the framework to integrate physical constraints and facilitating solutions for systems with robotic manipulators. Physical testing in a four-printer scenario with robotic arms confirms that SafeZone* enables collision-free printing, resulting in a printing time reduction of 44.63% when compared to the single-printer scenario. Finally, numerical studies reveal trends in the optimal solutions concerning the chromatic number of their resulting partition graphs and the distribution of the printing areas among printers. 

Abstract We present NoodlePrint, a generalized computational framework for maximally concurrent layer-wise cooperative 3D printing (C3DP) of arbitrary part geometries with multiple robots. NoodlePrint is inspired by a recently discovered set of helically interlocked space-filling shapes called VoroNoodles. Leveraging this unique geometric relationship, we introduce an algorithmic pipeline for generating helically interlocked cellular segmentation of arbitrary parts followed by layer-wise cell sequencing and path planning for cooperative 3D printing. Furthermore, we introduce a novel concurrence measure that quantifies the amount of printing parallelization across multiple robots. Consequently, we integrate this measure to optimize the location and orientation of a part for maximally parallel printing. We systematically study the relationship between the helix parameters (i.e., cellular interlocking), the cell size, the amount of concurrent printing, and the total printing time. Our study revealed that both concurrence and time to print primarily depend on the cell size, thereby allowing the determination of interlocking independent of time to print. To demonstrate the generality of our approach with respect to part geometry and the number of robots, we implemented two cooperative 3D printing systems with two and three printing robots and printed a variety of part geometries. Through comparative bending and tensile tests, we show that helically interlocked part segmentation is robust to gaps between segments. 

Machine learning (ML) algorithms have advanced significantly in recent years, progressively evolving into artificial intelligence (AI) agents capable of solving complex, human-like intellectual challenges. Despite the advancements, the interpretability of these sophisticated models lags behind, with many ML architectures remaining black boxes that are too intricate and expansive for human interpretation. Recognizing this issue, there has been a revived interest in the field of explainable AI (XAI) aimed at explaining these opaque ML models. However, XAI tools often suffer from being tightly coupled with the underlying ML models and are inefficient due to redundant computations. We introduce provenance-enabled explainable AI (PXAI). PXAI decouples XAI computation from ML models through a provenance graph that tracks the creation and transformation of all data within the model. PXAI improves XAI computational efficiency by excluding irrelevant and insignificant variables and computation in the provenance graph. Through various case studies, we demonstrate how PXAI enhances computational efficiency when interpreting complex ML models, confirming its potential as a valuable tool in the field of XAI. 

Abstract Swarm manufacturing (SM) is an emerging manufacturing paradigm that employs a heterogeneous swarm of robots to accomplish complex hybrid manufacturing tasks. Cooperative 3D Printing (C3DP), a special form of swarm manufacturing, uses multiple printers to print large-scale parts cooperatively and aims to tackle key challenges in the additive manufacturing industry, such as trade-offs among size, speed, quality, and cost. A fundamental challenge in C3DP is how to achieve collision-free, time-efficient printing when multiple printers operate in a shared workspace. This is a complex problem since the solution may depend on a myriad of factors, such as the number of printers, part geometry, printer positioning, mobility, and kinematics, or whether the printing path pre-determined. In this paper, we present SafeZone, a collision-free and scalable C3DP framework that aims to minimize printing time by considering both the geometry and topology (space-connectivity) of the resulting workspace when segmenting the part layer. To achieve this, we use a guided Voronoi tessellation that can only produce degree-3 partitions, which we show to have optimal scheduling properties based on the chromatic number of the resulting partition graph. The sites of the Voronoi tessellation are constrained to only lie on the boundary of their convex hull, thus facilitating collision-free operation in C3DP systems with robotic arms. We demonstrate through physical testing in a 4-printer scenario with SCARA arms that SafeZone can produce collision-free prints, resulting in a printing time reduction of 44.63% when compared to the single-printer scenario. Finally, we show how the partition created by our methodology has a printing time reduction of 22.83% when compared to a naive choice which does not consider workspace topology. 

Effective vector representation models, e.g., word2vec and node2vec, embed real-world objects such as images and documents in high dimensional vector space. In the meanwhile, the objects are often associated with attributes such as timestamps and prices. Many scenarios need to jointly query the vector representations of the objects together with their attributes. These queries can be formalized as range-filtering approximate nearest neighbor search (ANNS) queries. Specifically, given a collection of data vectors, each associated with an attribute value whose domain has a total order. The range-filtering ANNS consists of a query range and a query vector. It finds the approximate nearest neighbors of the query vector among all the data vectors whose attribute values fall in the query range. Existing approaches suffer from a rapidly degrading query performance when the query range width shifts. The query performance can be optimized by a solution that builds an ANNS index for every possible query range; however, the index time and index size become prohibitive -- the number of query ranges is quadratic to the number n of data vectors. To overcome these challenges, for the query range contains all attribute values smaller than a user-provided threshold, we design a structure called the segment graph whose index time and size are the same as a single ANNS index, yet can losslessly compress the n ANNS indexes, reducing the indexing cost by a factor of Ω(n). To handle general range queries, we propose a 2D segment graph with average-case index size O(n log n) to compress n segment graphs, breaking the quadratic barrier. Extensive experiments conducted on real-world datasets show that our proposed structures outperformed existing methods significantly; our index also exhibits superior scalability. 

Cooperative 3D Printing (C3DP), an additive manufacturing platform consisting of a swarm of mobile printing robots, is an emerging technology designed to address the size and printing speed limitations of conventional, gantry-based 3D printers. A typical C3DP process often involves several interconnected stages, including project/job partitioning, job placement on the floor, task scheduling, path planning, and motion planning. In our previous work on project partitioning, we presented a Z-Chunker, which vertically divides a tall print project into multiple jobs to overcome the physical constraints of printers in the Z direction, and an XY Chunker, to partition jobs into discrete chunks, which are allocated to individual printing robots for parallel printing. These geometry partitioning algorithms determine what is to be printed, but other information, such as when, where, and in what order chunks should be printed, is required to carry out the print physically. This paper introduces the first Job Placement Optimizer for C3DP based on Dynamic Dependency List schedule assignment and Conflict-Based Search path planning. Our algorithm determines the optimal locations for all jobs and chunks (i.e., subtasks of a job) on the factory floor to minimize the makespan for C3DP. To validate the proposed approach, we conduct three case studies: a simple geometry with homogeneous jobs in the Z direction and two complex geometries (one with moderate complexity and one relatively more complex) with non-homogeneous jobs in the Z direction. We also performed simulations to understand the impact of other factors, such as the number of robots, the number of jobs, chunking orientation, and the heterogeneity of prints (e.g., when chunks are different in size and materials), on the effectiveness of this placement optimizer. 

Abstract One of the major challenges in 3D printing is its lack of scalability both in size and speed, which directly impacts its economic feasibility for large-scale industrial applications. Cooperative 3D printing (C3DP) is an emerging paradigm that aims to address these issues by employing multiple mobile printers that work in parallel. However, a crucial step in enabling C3DP is the development of a collision-free communication framework between the printers during the manufacturing process. Many C3DP systems found in the literature develop solutions for collision-free printing that are specific to the setup being used, thus not allowing the solution to be transferred to other similar systems. In this paper, we formulate a general framework that generates four distinct collision-free communication strategies to enable arm-arm coordination for C3DP using robotic manipulators. We considered collisions both between the arms with themselves and between the arms and the part being printed. The strategies are general in that they are agnostic to the number of printers, their kinematics, and their spatial configurations in the manufacturing environment. We conducted a study of the four strategies using a two-printer scenario and then physically validated them with four test cases of varying geometries. The results show that the strategies successfully produce printed parts while being collision-free. The makespan reduction using our strategies when compared to a single printer varied from 20% to 42% depending on the strategy used. Finally, we discuss the limitations of the framework, as well as future research directions. 

Abstract In this paper, we present a decentralized approach based on a simple set of rules to schedule multi-robot cooperative additive manufacturing (AM). The results obtained using the decentralized approach are compared with those obtained from an optimization-based method, representing the class of centralized approaches for manufacturing scheduling. Two simulated case studies are conducted to evaluate the performance of both approaches in total makespan. In the first case, four rectangular bars of different dimensions from small to large are printed. Each bar is first divided into small subtasks (called chunks), and four robots are then assigned to cooperatively print the resulting chunks. The second case study focuses on testing geometric complexity, where four robots are used to print a mask stencil (an inverse stencil, not face covering). The result shows that the centralized approach provides a better solution (shorter makespan) compared to the decentralized approach for small-scale problems (i.e., a few robots and chunks). However, the gap between the solutions shrinks while the scale increases, and the decentralized approach outperforms the centralized approach for large-scale problems. Additionally, the runtime for the centralized approach increased by 39-fold for the extra-large problem (600 chunks and four robots) compared to the small-scale problem (20 chunks and four robots). In contrast, the runtime for the decentralized approach was not affected by the scale of the problem. Finally, a Monte-Carlo analysis was performed to evaluate the robustness of the centralized approach against uncertainties in AM. The result shows that the variations in the printing time of different robots can lead to a significant discrepancy between the generated plan and the actual implementation, thereby causing collisions between robots that should have not happened if there were no uncertainties. On the other hand, the decentralized approach is more robust because a collision-free schedule is generated in real-time.